Static Search Trees와 나의 트리

2025/01/02

원글 : https://news.hada.io/topic?id=18540&fbclid=IwY2xjawHjJv5leHRuA2FlbQIxMQABHXxu41OZlCal8J2w6IneXitgSfFZylPwxHWV8NLwGjPO_cyRCMvbR8NZLQ_aem_NHh_m-PJjOIOvBcKFeemdw

나도 비슷한(... 많이 다를 지도...) 것을 깔짝깔짝 취미로 건들건들 해 본 적이 있다. 지금 이 시점에서 코드로 남은 것은 찾을 수 없지만.. 아이디어는 이렇다.

1. 밸런스드 트리를 구현하는 것은 내 능력에서 어려우니까 리눅스 커널에서 RB-Tree를 뜯어온다. 스케쥴러의 그것. 요즘 스케쥴러는 모른다.
2. 멀티쓰레딩을 효과적으로 구현하고, 트리 뎁쓰를 낮추기 위해 루트 노드 수준에서 트리를 여러벌로 분산 시킨다. 이 때 컨텍스트의 특징에 따라 분산 해싱 방법은 따로 고안한다. 원래는 통계적 방법론으로 트리 벌 수와 루트 노드의 데이터를 결정하고자 했다. 트리 뎁쓰를 낮추는 것이 사실 큰 도움이 안 될 수는 있는데, 도메인에 따라서는 (생략)
3. 트리 순회는 캐시와 인스트럭션 파이프가 깨지기 쉽고, 컴파일러가 SIMD를 효과적으로 가져가지 못할 가능성이 크다. 따라서 각 트리는 선형으로 전개한 소팅된 벡터를 따로 한 벌 더 갖는다. 메모리는 더 많이 먹는다. 포인터만 찍어두는 방법이 있지만 compare를 위해 컨텍스트를 가져올 때 랜덤 액세스가 되므로 더 이상의 고민은 능력 밖이라 데이터도 같이 넣는다.
4. 순차 루핑 작업이 필요할 때 벡터로 처리하고 정확한 검색이 필요할 때 트리로 처리한다. 트리로 찾은 후 벡터의 인덱스를 구해서 거기서 부터 앞 뒤 순차 루핑 처리를 할 수도 있다.
5. 4번을 처리함에 있어 인텔 intrinsics 함수를 동원해 avx, simd 명령어로 손 최적화를 동원한다.
6. 5번을 시행함에 있어 gcc -O3가 나보다 스마트할 때가 많다는 것을 알았다. O3를 해보고 -S로 어셈블러 코드를 본 후 내가 직접 개입할 부분만 고친다. 결과적으로 이 작업은 intrinsics를 한 땀 한 땀 처리하기 보다는 컴파일러가 더 잘 최적화하기 위한 실험으로 변해갔다.

김윤수 님이 이 때 조언을 주셨다. 핳핳핳.. C++을 잘 못하지만 김윤수님의 이상계 블로그들을 보곤 했던 것 같다.

나는 아직도 intrinsics 철자를 외우지 못한다... 하아..

[t:/] is not "technology - root". dawnsea, rss